package com.dmall.play.interview.chapter08;

import java.util.*;

public class Leetcode47V1 {

    private Set<String> existSet;
    private List<List<Integer>> ans = null;
    private boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null) {
            return null;
        }
        ans = new ArrayList<>();
        visited = new boolean[nums.length];
        existSet = new HashSet<>();
        if (nums.length == 0) {
            return ans;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        findPermute(nums, 0, stack, sb);
        return ans;
    }

    private void findPermute(int[] nums, int index, Deque<Integer> stack, StringBuilder sb) {
        if (index == nums.length) {
            if (!existSet.contains(sb.toString())) {
                existSet.add(sb.toString());
                ans.add(new ArrayList<>(stack));
            }
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                stack.add(nums[i]);
                visited[i] = true;
                sb.append(nums[i]);
                findPermute(nums, index + 1, stack, sb);
                visited[i] = false;
                sb.deleteCharAt(sb.length() - 1);
                stack.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Leetcode47V1 leetcode = new Leetcode47V1();
        int[] nums = {-1, 2, -1, 2, 1, -1, 2, 1};
        long start = System.currentTimeMillis();
        List<List<Integer>> res = leetcode.permuteUnique(nums);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        System.out.println(res.size());
        System.out.println(res);
    }
}
